package LeetcodeTest_six;
//整数替换
public class integerReplacement
{
    public static void main(String[] args)
    {
        System.out.println(solution.integerReplacement(65535));
    }
}
class solution
{
    public static int integerReplacement(int n)
    {
        int i;
        i=0;
        while(n!=1)
        {
            if (n % 2 != 0)
            {
                if (n<=3)
                    i=i+n-1;
                else if(n==Integer.MAX_VALUE)
                    return 32;
                else if((n+1)%4==0)
                {
                    n = n + 1;
                    i++;
                }
                else
                {
                    n = n - 1;
                    i++;
                }
                n=n/2;
                i++;
            }
            if (n % 2 == 0)
            {
                n = n / 2;
                i++;
            }
        }
        return i;
    }
}